Polynomial commitment scheme

• Polynomial commitment schemes[KZG,10]
  • $keygen(\lambda ,\mathcal{F})\to gp$:
  • $commit(gp,f)\to C_f$
  • $eval(gp,f,u)\to v,\pi$:
  • $verify(gp,C_f,u,v,\pi )$:
• Opening many polynomials at $s$
  • Naive solution
  • Batched opening
• open a polynomial $f$ at points $s_0,\dots ,s_{d-1}$
• KZG Ceremony

Polynomial commitment schemes[KZG,10]

Bilinear Group: $p,{\mathbb{G}}_1,{\mathbb{G}}_2,{\mathbb{G}}_{\mathbb{T}},G_1,G_2,e$ Univariate polynomials $\mathcal{F}={\mathbb{F}}_p^{(\le d)}[X]$

$keygen(\lambda ,\mathcal{F})\to gp$:

• Sample random $\tau \in {\mathbb{F}}_p$
• $gp=((G_1,[\tau ]G_1,[{\tau }^2]G_1,\dots ,[{\tau }^d]G_1),(G_2,[\tau ]G_2))$
• delete $\tau$ !! (trusted setup)

$commit(gp,f)\to C_f$

• $f(x)=f_0+f_{1}x+f_2{x}^2+\cdots +f_d{x}^d$
• $C_f=[f(\tau )]G_1=[f_0+f_1\tau +f_2{\tau }^2+\cdots +f_d{\tau }^d]G_1=[f_0]G_1+[f_1]\tau G_1+[f_2]{\tau }^2{G}_1+\cdots +[f_d]{\tau }^d{G}_1$

Honest prover: $C_f=[f(\tau )]G_1,\pi =[q(\tau )]G_1,v=f(u)$

$eval(gp,f,u)\to v,\pi$:

• $f(x)-f(u)=(x-u)q(x)$, as $u$ is a root of $f(x)-f(u)$
• Compute $q(x)$ and $\pi =[q(\tau )]G_1$, using gp

$verify(gp,C_f,u,v,\pi )$:

check $e(C_f-[v]G_1,G_2)\stackrel{?}{=}e(\pi ,[\tau ]G_2-[u]G_2)$

Opening many polynomials at $s$

Input: ${\mathbf{f}}_0,{\mathbf{f}}_1,\dots ,{\mathbf{f}}_{\mathbf{k}-1},Z_0={\mathbf{f}}_0(s),z_1={\mathbf{f}}_1(s),\dots ,z_{k-1}={\mathbf{f}}_{\mathbf{k}-1}(s)$.
Verifier has commitments $C_{\mathbf{f}}$ to ${\mathbf{f}}_{\mathbf{i}}$'s wants to verifier correctness of $z$'s.

Naive solution

Run KZG for each ${\mathbf{f}}_{\mathbf{i}}$. Cost: $d$ group elemets in proof, $d$ pairings for verifier.

Batched opening

• Verifier sends random $\gamma \in {\mathbb{F}}_p$
• Prover computes combination $\mathbf{f}(\mathbf{X}):={\sum }_{\mathbf{i}<\mathbf{k}}{\gamma }^{\mathbf{i}}{\mathbf{f}}_{\mathbf{i}}(\mathbf{X})$
• Verifier computes commitment to $\mathbf{f}$ as $C_{\mathbf{f}}:={\sum }_{i<k}{\gamma }^i{C}_{{\mathbf{f}}_{\mathbf{i}}}$
• Prover and verifier use KZG to verify $\mathbf{f}(\mathbf{s})=z$ for $z={\sum }_{i<k}{\gamma }^i{z}_i$
  Cost: $k-1$ verifier scalar muls to compute $C_{\mathbf{f}}$

open a polynomial $f$ at points $s_0,\dots ,s_{d-1}$

thm[BDFG]: We can open a polynomial $\mathbf{f}$ at points $s_0,s_1,\dots ,s_{k-1}$ with 2 verifier scalar mults no matter how large $k$ is.

KZG Ceremony

A distributed generation of $gp$ s.t. no one can reconstruct the trapdoor if at least one of the participants is honest and discards their secrets.

• $gp=(G,\tau G,{\tau }^{2}G,\dots ,{\tau }^{d}G)=(G_0,G_1,G_2,\dots ,G_d)$
• Sample random $s$, update $g{p}^{\prime }=(G_0,G_1^{\prime },G_2^{\prime },\dots ,G_d^{\prime })=(G_0,s{G}_1,s^2{G}_2,\dots ,s^d{G}_d)$ with secret $\tau \cdot s$!
• Check the correctness of $g{p}^{\prime }$
  • The contributor knows $s$ s.t. $G_1^{\prime }=s{G}_1$
  • $g{p}^{\prime }$ consists of consecutive powers $e(G_i^{\prime },G_1^{\prime })=e(G_{i+1}^{\prime },G)$ and $G_1^{\prime }\ne O$